package 动态规划;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @description:
 * @author: ywk
 * @date: 2020-12-19
 */
@Slf4j
public class 找硬币 {
    static int amount = 7;
    static int[] memo = new int[amount + 1];
    static int[] nums = {3, 6, 2, 1};

    public static void main(String[] args) {
        System.out.println(coinChange(nums, amount));
    }


    ////自顶向下
    public static int coinChange(int[] nums, int amount) {
        if (amount == 0) {
            return 0;
        }
        if (memo[amount] != 0) {
            return memo[amount];
        }
        int res = Integer.MAX_VALUE;
        for (int num : nums) {
            if (amount - num < 0) {
                continue;
            }
            res = Math.min(res, coinChange(nums, amount - num) + 1);
            memo[amount] = res;
        }
        return res;
    }
    //自底向上,一维数组
    public static int coinChangeDp(int[] nums, int amount) {
        int[] arr = new int[amount + 1];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.MAX_VALUE;
        }
        arr[0] = 0;
        for (int i = 0; i <= amount; i++) {
            for (int num : nums) {
                if (i - num >= 0) {
                    arr[i] = Math.min(arr[i], 1 + arr[i - num]);
                }
            }
        }
        return arr[amount];
    }
}
